package mine.code.day.year2021.month09;

import org.junit.Test;

/**
 * 给定两个单词word1和word2，找到使得word1和word2相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
 * <p>
 * 示例：
 * <p>
 * 输入: "sea", "eat"
 * 输出: 2
 * 解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
 *
 * @author caijinnan
 */
public class Day25_两个字符串的删除操作 {

    @Test
    public void run() {
        String word1 = "q";
        String word2 = "d";
        System.out.println(minDistance(word1, word2));
    }

    public int minDistance(String word1, String word2) {
        int w1Length = word1.length();
        int w2Length = word2.length();
        char[] w1Chars = word1.toCharArray();
        char[] w2Chars = word2.toCharArray();
        int[][] dp = new int[w1Length + 1][w2Length + 1];
        dp[0][0] = 0;
        for (int i = 1; i <= w1Length; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= w2Length; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= w1Length; i++) {
            for (int j = 1; j <= w2Length; j++) {
                dp[i][j] = w1Chars[i - 1] == w2Chars[j - 1] ? dp[i - 1][j - 1] : (Math.min(dp[i - 1][j], dp[i][j - 1]) + 1);
            }
        }
        return dp[w1Length][w2Length];
    }
}
